package 华为OD机试真题2023.基础题;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class HJ28_最左侧冗余覆盖子串 {
  public static void main(String[] args) throws FileNotFoundException {
    Scanner in = new Scanner(new File("src/main/java/华为OD机试真题2023/基础题/input/28.txt"));
    String s1 = in.nextLine();
    String s2 = in.nextLine();
    int k = in.nextInt();
    int len = s1.length() + k;
    if (len > s2.length()) {
      System.out.println(-1);
      return;
    }
    int[] cntS1 = new int[26];
    getCharCount(cntS1, s1);
    int[] cntStrSub = new int[26];
    for (int i = 0; i <= s2.length() - len; i++) {
      String strSub = s2.substring(i, len);
      getCharCount(cntStrSub, strSub);
      if (isMatch(cntS1, cntStrSub)) {
        System.out.println(i);
        return;
      }
    }
    System.out.println(-1);
  }

  static void getCharCount(int[] cnt, String s) {
    for (int i = 0; i < s.length(); i++) {
      cnt[s.charAt(i) - 'a']++;
    }
  }

  static boolean isMatch(int[] cnt1, int[] cntSub) {
    for (int i = 0; i < 26; i++) {
      if (cnt1[i] > cntSub[i]) {
        return false;
      }
    }
    return true;
  }
}
